package dp;

/**
 * 减法和加法的相减之后等于target
 * + : x, - : sum - x;
 * target = x -( sum - x )
 * x = ( target + sum ) / 2
 * 之后就是装满背包 x 的种类树，这是组合问题
 * dp[j] += dp[j - nums[i]];
 */
public class ds494_目标和 {
    public static void main(String[] args) {
        System.out.println(findTargetSumWays(new int[]{1,1,1,1,1}, 3));
    }

    public static int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(Math.abs(target) > sum || (target + sum) % 2 == 1)
            return 0;
        int t = (target + sum) / 2;
        int[] dp = new int[t + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = t; j >= nums[i] ; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[t];
    }

    static int s = 0;
    public static int findTargetSumWays_dfs(int[] nums, int target) {
        dfs(nums, target, 0, 0);
        return s;
    }
    public static void dfs(int[] nums, int target, int i, int sum){
        if(sum == target && i == nums.length){
            s++;
            return;
        }
        if(i == nums.length)
            return;
        dfs(nums, target, i + 1, sum + nums[i]);
        dfs(nums, target, i + 1, sum - nums[i]);
    }
}
